﻿// #define_CRT_SECURE_NO_WARNINGS 1	
     # 1. 柠檬水找零（easy）
     https ://leetcode.cn/problems/lemonade-change/submissions/586140681/

 ```cpp
     class Solution {
     public:
         bool lemonadeChange(vector<int>& bills) {
             //尽可能少的利用五元找零
             //证明：交换论证法
             //最优解与贪心解不同时，最优解能替换成贪心解且不少最优性
             //找零情况：5收下找0,10收下找5,20收下找5和10或者三张5
             //当贪心解与最优解不同时也就是最优解利用两张5而不是一张10时，最优解将两张5换成10
             //分为两种情况：
             //有剩下的10没用到直接拿来用
             //后面用到了直接替换，与贪心解相同找零仍然正确
             int five_count = 0, ten_count = 0, twenty_count = 0;
             int n = bills.size();
             for (int i = 0; i < n; i++)
             {
                 if (bills[i] == 5)
                 {
                     five_count++;
                 }
                 else if (bills[i] == 10 && five_count)
                 {
                     ten_count++;
                     five_count--;
                 }
                 else if (bills[i] == 20 && five_count && ten_count)
                 {
                     twenty_count++;
                     five_count--;
                     ten_count--;
                 }
                 else if (bills[i] == 20 && five_count >= 3)
                 {
                     twenty_count++;
                     five_count -= 3;
                 }
                 else
                     return false;
             }
             return true;
         }
 };
 ```


     # 2. 将数组和减半的最少操作次数（medium）
     https ://leetcode.cn/problems/minimum-operations-to-halve-array-sum/submissions/586143137/

 ```cpp
     class Solution {
     public:
         int halveArray(vector<int>& nums) {
             //贪心策略：对最大的数除于2求和
             //证明方法：交换论证法
             //略
             //防止除2后重复找最大，我们借用优先队列
             priority_queue<double> heap;
             double sum = 0;
             for (auto element : nums)
             {
                 sum += element;
                 heap.push(element);
             }
             double target = sum / 2;
             int count = 0;
             while (sum > target)
             {
                 count++;
                 double top = heap.top();
                 sum -= top;
                 heap.pop();
                 top /= 2;
                 sum += top;
                 heap.push(top);
             }
             return count;
         }
 };
 ```

     # 3. 最⼤数（medium）

     https ://leetcode.cn/problems/largest-number/submissions/586146527/

 ```cpp
     class Solution {
     public:
         string largestNumber(vector<int>& nums) {
             //贪心，排序，证明也是交换论证法
             //数a,数b
             //排序规则为：ab>ba,按降序排
                         // ab=ba不交换
                          //ab<ba,交换ab的位置
                          //难点在排序条件适用如何证明

             struct myclass {
                 bool operator() (string& a, string& b) {
                     return a + b > b + a;//字典序比较
                 }
             }myobject;

             vector<string> strs;
             for (auto ch : nums)
             {
                 strs.push_back(to_string(ch));
             }
             sort(strs.begin(), strs.end(), myobject);
             string ret;
             for (auto str : strs)
                 ret += str;

             if (ret[0] == '0')//特殊情况，字符串可能为"0000".此时返回"0"
                 return "0";
             return ret;
         }
 };
 ```